package 链表;

/**
 * 82. 删除排序链表中的重复元素 II
 *
 * 解题思路：
 *  1.使用哑节点（Dummy Node）：为了方便处理头节点可能被删除的情况，我们可以在链表前面添加一个哑节点。
 *  2.双指针法：使用两个指针 prev 和 curr，prev 指向当前处理节点的前一个节点，curr 指向当前处理的节点。
 *  3.遍历链表：遍历链表，检查当前节点 curr 和下一个节点 curr.next 的值是否相同。如果相同，则继续向后遍历，直到找到不相同的节点，然后将 prev.next 指向这个不相同的节点。如果不同，则直接移动 prev 和 curr。
 *  4.返回结果：最终返回哑节点的下一个节点，即处理后的链表的头节点。
 *
 */
public class L_82 {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }

        // 创建一个哑节点，方便处理头节点可能被删除的情况
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode curr = head;

        while (curr != null){
            // 如果当前节点和下一个节点的值相同，则继续向后遍历，直到找到不相同的节点
            while (curr.next != null && curr.val == curr.next.val){
                curr = curr.next;
            }
            // 如果prev.next == curr,证明curr没有重复，直接移动前置节点pre
            if(prev.next == curr){
                prev = curr;
            }else {
                // 否则，跳过所有重复的节点
                prev.next = curr.next;
            }
            // 移动当前节点继续遍历
            curr = curr.next;
        }
        // 返回结果
        return dummy.next;
    }


    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
}
